package DataStructure.TreeLearning.BinarySortTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class MyBinarySortTreeImpl<Item extends Comparable<Item>> implements  MyBinarySortTree<Item>{
    // 设置树的根节点
    private Node root;
    // 设置树元素数量
    private int size;

    /**
     *  添加元素
     * @param item 添加的元素
     * @return  返回成功与否
     */
    @Override
    public boolean add(Item item) {
        // 判断元素是否为空值
        if(item == null) {
            throw new IllegalArgumentException("The parame is null");
        }
        // 判断树是否为空
        if(size == 0) {
            // 若原树为空，则给root赋值，size++
            root = new Node(null, item, null);
            size++;
            return true;
        }
        // 原树不为空，则添加的位置是叶子节点
        // 设置两个标记节点
        Node mid = root;
        Node midFather = null;
        // 比较新元素与标记节点的值
        int compare = 0;
        while(mid != null) {
            compare = item.compareTo(mid.value);
            if(compare == 0) {
                // 当发现重复元素时，返回false，不存值
                return false;
            } else if(compare < 0) {
                // <0 表示新元素小于标记节点，应该向左子树继续遍历
                // 先保存标记节点，用于后面添加操作
                midFather = mid;
                mid = mid.leftChild;
            } else {
                // >0 表示新元素大于标记节点，向右子树遍历
                midFather = mid;
                mid = mid.rightChild;
            }
        }
        // 跳出循环时，mid指向null，而midFather指向最后的节点
        // 需要将新元素添加到midFather后面
        // 但此时不知道新元素和midFather的大小关系，还要再比较一次
        if(compare < 0) {
            midFather.leftChild = new Node(null, item, null);
        } else {
            midFather.rightChild = new Node(null, item, null);
        }
        size++;
        return true;
    }

    /**
     *  删除功能
     * @param item  需要删除的元素
     * @return  返回成功与否
     */
    @Override
    public boolean remove(Item item) {
        // 如果树为空，则报错
        if(size == 0) {
            throw new RuntimeException("The BSTree is null");
        }
        // 设置两个标记节点
        Node mid = root;
        Node midFather = null;
        int compare = 0;
        // 遍历查找指定节点
        while(mid != null) {
            compare = item.compareTo(mid.value);
            if(compare == 0) {
                // 找到则跳出循环
                break;
            } else if(compare < 0) {
                midFather = mid;
                mid = mid.leftChild;
            } else {
                midFather = mid;
                mid = mid.rightChild;
            }
        }
        // 跳出循环有两个可能
        // 1. mid指向null，表示没有找到指定元素
        if(mid == null) {
            return false;
        }
        // 2. 否则则找到，并且mid指向需要删除的元素

        // 此时需要删除的元素有三种情况
        // 1. 该元素左右孩子节点均不为空，是双分支
        // 2. 该元素只有左孩子节点或者只有右孩子节点，是单分支
        // 3. 该元素没有左右孩子节点，是叶子节点

        // 先处理双分支节点 -- 可以将双分支节点问题转换为单分支或者叶子
        if(mid.leftChild != null && mid.rightChild != null) {
            // 设置两个标记节点，查找该节点左子树中的最大值用来替换
            Node max = mid.leftChild;
            Node maxFather = mid;
            // 遍历左子树中的最大值，要在右边查找
            while(max.rightChild != null) {
                maxFather = max;
                max = max.rightChild;
            }
            // 此时max就是用来替换的节点
            mid.value = max.value;
            // 将mid和midFather指向max及maxFather
            // 在后面利用单分支或叶子处理 删除max节点即可
            mid = max;
            midFather = maxFather;
        }

        // 到这里，mid指向的节点或者是叶子节点，或者是单分支节点
        // 如果是单分支节点，就要获取它的子树（左或右）
        // 这条语句的意思：如果mid的左孩子节点为空，则返回mid的右孩子节点，
        //              若右孩子结点也为空则mid是叶子节点；
        //              否则返回左孩子节点。
        Node child = mid.leftChild == null ? mid.rightChild : mid.leftChild;

        // 当需要删除的是root,且root为单分支时
        // midFather始终指向null，此时可以直接将child赋值给root
        if(midFather == null) {
            root = child;
            size--;
            return true;
        }

        if(midFather.leftChild == mid) {
            // 若mid是midFather的左孩子节点，则将midFather的左孩子节点越过mid赋给child
            midFather.leftChild = child;
        } else {
            midFather.rightChild = child;
        }
        size--;
        return true;
    }

    /**
     *  删除元素 -- 递归实现
     * @param item  要删除的元素
     * @return  返回成功与否
     */
    @Override
    public boolean remove_Recursion(Item item) {
        // 判断参数是否为空
        if (item == null) {
            throw new IllegalArgumentException("The parame is null");
        }
        // 判断树是否为空
        if(size == 0) {
            throw new RuntimeException("The tree is null");
        }
        // 判断树中是否包含该元素
        if( !contains(item) ) {
            return false;
        }
        root = remove_Recursion(root, item);
        size--;
        return true;
    }

    private Node remove_Recursion(Node root, Item item) {
        // 递归出口
        if(root == null) {
            return null;
        }
        // 判断大小
        int compare = item.compareTo(root.value);
        // <0 表示应在左子树寻找
        if(compare < 0) {
            root.leftChild = remove_Recursion(root.leftChild, item);
        } else if(compare > 0) {
            // >0 表示应在左子树寻找
            root.rightChild =  remove_Recursion(root.rightChild, item);
        } else {
            // 此时找到要删除的节点
            // 如果该节点是叶子节点或者单分支节点
            // 直接将该节点的孩子节点return出去
            if(root.leftChild == null || root.rightChild == null) {
               return root.leftChild == null ? root.rightChild : root.leftChild;
            }

            // 处理双分支节点 方式一：
        /*
            // 执行到这里表示，要删除的节点是双分支节点
            // 创建一个标记节点
            Node mid = root;
            // 找到这个节点左子树的最大值
            // 将要删除的节点替换成左子树的最大值的节点
            // 此时问题转换成删除左子树的最大值
            root = max(mid.leftChild);
            // 删除左子树的最大值
            root.leftChild = deleteMax(mid.leftChild);
            // 将原本删除的节点的右子树赋给现在的节点
            root.rightChild = mid.rightChild;
        */

            // 处理双分支节点 方式二：
            Item val = max(root.leftChild).value;
            root.value = val;
            root.leftChild = remove_Recursion(root.leftChild, val);
        }
        return root;
    }
    // 删除最大值节点
    private Node deleteMax(Node mid) {
        // 递归出口
        // 当右节点为null时，此节点是最大值
        // 因为此节点可能有左子树
        // 将此节点的左子树return出去
        if(mid.rightChild == null) {
            return mid.leftChild;
        }
        // 将return回来的节点赋给目前节点的右子树
        mid.rightChild = deleteMax(mid.rightChild);
        return mid;
    }
    // 寻找最大值节点
    private Node max(Node mid) {
        // 递归出口
        // 当右节点为null时，表示此节点是最大值
        if(mid.rightChild == null) {
            return mid;
        }
        return max(mid.rightChild);
    }

    /**
     *  查找功能
     * @param item  需要查找的元素
     * @return 返回是否存在
     */
    @Override
    public boolean contains(Item item) {
        // 若树为空，则报错
        if(size == 0) {
            throw new RuntimeException("The BSTree is null");
        }
        // 设置标记节点和比较结果
        Node mid = root;
        int compare = 0;
        while(mid != null) {
            compare = item.compareTo(mid.value);
            // 当相等时退出方法返回true
            if(compare == 0) {
                return true;
            } else if(compare < 0) {
                // <0 表示查询的数字在该节点的左子树，继续遍历
                mid = mid.leftChild;
            } else {
                // >0 表示查询的数字在该节点的右子树，继续遍历
                mid = mid.rightChild;
            }
        }
        // 退出循环则表示没有找到元素，返回false
        return false;
    }

    /**
     *  按前序遍历 -- 栈实现
     * @return  返回存有元素的List集合
     */
    @Override
    public List<Item> preOrder_Stack() {
        List<Item> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        // 循环判断 栈非空时
        while(!stack.isEmpty()) {
            Node pop = stack.pop();
            list.add(pop.value);
            // 将右子树先压入栈底
            if(pop.rightChild != null) {
                stack.push((pop.rightChild));
            }
            // 左子树在栈中较上位置
            if(pop.leftChild != null) {
                stack.push(pop.leftChild);
            }
        }
        return list;
    }

    /**
     *  按前序遍历 -- 递归实现
     * @return  返回存有元素的List集合
     */
    @Override
    public List<Item> preOrder_Recursion() {
        List<Item> list = new ArrayList<>();
        preOrder_Recursion(list, root);
        return list;
    }
    private void preOrder_Recursion(List list, Node root) {
        if(root == null) {
            return;
        }
        list.add(root.value);
        preOrder_Recursion(list, root.leftChild);
        preOrder_Recursion(list, root.rightChild);
    }

    /**
     *  按中序遍历 -- 栈实现
     * @return  返回存有元素的List集合
     */
    @Override
    public List<Item> inOrder_Stack() {
        List<Item> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();

        // 创建标记节点
        Node mid = root;

        // 大循环
        while (mid != null || !stack.isEmpty()){
            // 小循环
            while (mid != null){
                stack.push(mid);
                mid = mid.leftChild;
            }

            Node pop = stack.pop();
            list.add(pop.value);

            mid = pop.rightChild;
        }
        return list;
    }

    /**
     *  按中序遍历 -- 递归实现
     * @return  返回存有元素的List集合
     */
    @Override
    public List<Item> inOrder_Recursion() {
        List<Item> list = new ArrayList<>();
        inOrder_Recursion(list, root);
        return list;
    }
    private void inOrder_Recursion(List list, Node root) {
        if(root == null) {
            return;
        }
        inOrder_Recursion(list, root.leftChild);
        list.add(root.value);
        inOrder_Recursion(list, root.rightChild);
    }

    /**
     *  按后序遍历 -- 栈实现
     * @return  返回存有元素的List集合
     */
    @Override
    public List<Item> postOrder_Stack() {
        List<Item> list = new ArrayList<Item>();
        Stack<Node> stack = new Stack<>();
        // 将root压入栈中
        stack.push(root);
        // 循环判断 栈非空时
        while(!stack.isEmpty()) {
            Node pop = stack.pop();
            // 头插法
            list.add(0,pop.value);
            if(pop.leftChild != null) {
                stack.push(pop.leftChild);
            }
            if(pop.rightChild != null) {
                stack.push((pop.rightChild));
            }
        }
        return list;
    }

    /**
     *  按后序遍历 -- 递归实现
     * @return  返回存有元素的List集合
     */
    @Override
    public List<Item> postOrder_Recursion() {
        List<Item> list = new ArrayList<>();
        postOrder_Recursion(list, root);
        return list;
    }
    private void postOrder_Recursion(List list, Node root) {
        if(root == null) {
            return;
        }
        postOrder_Recursion(list, root.leftChild);
        postOrder_Recursion(list, root.rightChild);
        list.add(root.value);
    }

    /**
     *  按层级遍历
     * @return  返回存有元素的List集合
     */
    @Override
    public List<Item> levelOrder_Queue() {
        List<Item> list = new ArrayList<>();
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            Node poll = queue.poll();
            list.add(poll.value);
            if(poll.leftChild != null) {
                queue.offer(poll.leftChild);
            }
            if(poll.rightChild != null) {
                queue.offer(poll.rightChild);
            }
        }
        return list;
    }

    @Override
    public void buildTreeByInAndPost(List<Item> inOrder, List<Item> postOrder) {
        root = buildTreeByInAndPost_Recursion(inOrder, postOrder);
        size = inOrder.size();
    }
    private Node buildTreeByInAndPost_Recursion(List<Item> inOrder, List<Item> postOrder) {
        // 递归出口
        // 判断序列是否为空，空则返回null
        if(inOrder.size() == 0) {
            return null;
        }
        // 如果序列中只剩下最后一个元素，则建立最后的节点并结束递归
        if(inOrder.size() == 1) {
            return new Node(null, inOrder.get(0), null);
        }
        // 获取根节点元素，在后序的最后一个元素
        Item rootValue = postOrder.get(postOrder.size() - 1);
        // 根据根节点元素获取它在中序的下标
        int index = inOrder.indexOf(rootValue);
        // 根据下标位置划分左子树和右子树
        // 左子树：中序：0 ~ index-1
        //       后序：0 ~ index-1
        // 右子树：中序：index+1 ~ size-1
        //       后序：index ~ size-2
        List<Item> listLeftInOrder = inOrder.subList(0, index);
        List<Item> listLeftPostOrder = postOrder.subList(0, index);
        List<Item> listRightInOrder = inOrder.subList(index+1, inOrder.size());
        List<Item> listRightPostOrder = postOrder.subList(index, postOrder.size()-1);

        Node node = new Node(null, rootValue, null);

        node.leftChild = buildTreeByInAndPost_Recursion(listLeftInOrder, listLeftPostOrder);
        node.rightChild = buildTreeByInAndPost_Recursion(listRightInOrder, listRightPostOrder);

        return node;
    }

    @Override
    public void buildTreeByPreAndIn(List<Item> preOrder, List<Item> inOrder) {
        root = buildTreeByPreAndIn_Recursion(preOrder, inOrder);
        size = inOrder.size();
    }

    private Node buildTreeByPreAndIn_Recursion(List<Item> preOrder, List<Item> inOrder) {
        // 递归出口
        // 判断序列是否为空，空则返回null
        if(inOrder.size() == 0) {
            return null;
        }
        // 如果序列中只剩下最后一个元素，则建立最后的节点并结束递归
        if(inOrder.size() == 1) {
            return new Node(null, inOrder.get(0), null);
        }
        // 获取根节点元素，在前序第一个元素
        Item rootValue = preOrder.get(0);
        // 根据根节点元素获取它在中序的下标
        int index = inOrder.indexOf(rootValue);
        // 根据下标位置划分左子树和右子树
        // 左子树：中序：0 ~ index-1
        //       前序：1 ~ index
        // 右子树：中序：index+1 ~ size-1
        //       前序：index+1 ~ size-1
        List<Item> listLeftInOrder = inOrder.subList(0, index);
        List<Item> listLeftPreOrder = preOrder.subList(1, index+1);
        List<Item> listRightInOrder = inOrder.subList(index+1, inOrder.size());
        List<Item> listRightPreOrder = preOrder.subList(index+1, preOrder.size());

        Node node = new Node(null, rootValue, null);

        node.leftChild = buildTreeByPreAndIn_Recursion(listLeftPreOrder, listLeftInOrder);
        node.rightChild = buildTreeByPreAndIn_Recursion(listRightPreOrder, listRightInOrder);

        return node;
    }


    class Node {
        Node leftChild;
        Item value;
        Node rightChild;

        public Node(Item value) {
            this.value = value;
        }

        public Node(Node leftChild, Item value, Node rightChild) {
            this.leftChild = leftChild;
            this.value = value;
            this.rightChild = rightChild;
        }
    }
}
